Лабораторная работа №6

Разложение чисел на множители

Тазаева Анастасия Анатольевна

Российский университет дружбы народов

2025-11-08

Информация

Докладчик

  • Тазаева Анастасия Анатольевна
  • студент группы НФИмд-02-25
  • Российский университет дружбы народов им. П. Лумумбы
  • 1032259385@pfur.ru

Введение

Цель работы

Ознакомиться с pho-методом Полларда. Реализовать его.

Задачи

  1. Реализовать на языке программирования Julia pho-метод Полларда.
  2. Разложить на множители число 1359331.

Теоретические сведения

Разложение на множители

pho-метод Полларда (или \(\rho-1\) метод Полларда) является одним из алгоритмов для факторизации целых чисел, который особенно эффективен для нахождения малых простых делителей. Он основан на свойствах чисел и использует последовательности, чтобы вычислить делители.

Основные этапы метода

  1. Подготовка:
    • Выбор числа n: Начинаем с целого числа n, которое необходимо факторизовать;
    • Выбор параметров: Выбираем небольшое целое число a и границу B, которая будет использоваться для ограничения множителей.
  2. Генерация последовательности: Создаем последовательность чисел по формуле: \(x_{k+1} = (x_k^2 + a)\).
  3. Вычисление НОД: На каждом шаге вычисляем наибольший общий делитель (НОД) между n и разностью двух членов последовательности.
  4. Проверка результата: Если найденный НОД d больше 1 и меньше n, то это делитель числа n. Если \(d = n\), то алгоритм не дал результата, и его можно повторить с другими параметрами. Если \(d=1\), то повторяем действия со второго шага.
  5. Завершение: Процесс продолжается до тех пор, пока не будет найден делитель или не исчерпаются все возможные варианты.

Программный код

pho-метод Полларда

function pollard(n, c, f::Function)
    # step 1
    a = c
    b = c
    # step 2-4
    println(a, "\t", b, "\t")
    while true
        # step 2
        a = f(a) % n
        b = f(b) % n
        b = f(b) % n 

pho-метод Полларда

        # step 3
        d = binary_gcd(abs(a-b),n)
        
        println(a, "\t", b, "\t", d)
        # step 4
        if 1 < d < n
            return d, round(Int, n/d)
        elseif d == n
            return "Delitel ne naiden"
        end
    end
end

pho-метод Полларда. Результат работы программного кода

Рисунок 1: pho-метод Полларда. Пример

Заключение

Вывод

В ходе лабораторной работы был изучен pho-метод Полларда.